package org.basis.algorithm.sort;

/**
 * 二分法查找局部最小值
 * 该问题说明不只是有序数组才能使用二分法
 *
 * @author Mr_wenpan@163.com 2021/12/03 09:38
 */
public class LocalMinimum {

    public static void main(String[] args) {
        int[] arr = {7, 6, 9, 17, 8, 9, 11};
        int min = process(arr);
        int min2 = process2(arr);
        System.out.println("min = " + min);
        System.out.println("min2 = " + min2);
    }

    /**
     * 用二分算法求局部最小值，时间复杂度O（logN）
     */
    private static int process(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        // 尾部为局部最小值
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr[arr.length - 1];
        }
        // 头部为局部最小值
        if (arr[0] < arr[1]) {
            return arr[0];
        }

        // 否则，（1, n - 2）中间范围必定存在局部最小值
        int left = 1;
        int right = arr.length - 2;
        int mid = left + (right - left) / 2;

        // 区间二分
        while (left < right) {
            // 左区间必有局部最小
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
                // 右空间必有局部最小
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                // 中点就是局部最小
                return arr[mid];
            }
            // 重置中点
            mid = (right + left) / 2;
        }

        return -1;
    }

    /**
     * 遍历算法求局部最小值，时间复杂度为O(n)
     */
    private static int process2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        // 尾部为局部最小值
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr[arr.length - 1];
        }
        // 头部为局部最小值
        if (arr[0] < arr[1]) {
            return arr[0];
        }

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                return arr[i];
            }
        }
        return -1;
    }
}
